package sortAlgorithm.mergeSort;


import java.util.Arrays;

/**
 * @author： pang-yun
 * @date： 2021-10-08 14:46
 * 功能目的 ：用于  归并排序
 */

public class MergeSortPro {


    public static void main(String[] args) {
        Integer[] arr={4,3,2,1};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }


    //归并所需要的辅助数组
    private static Comparable[] assist;

    // 比较v 的值 是否小于 w
    private static boolean less(Comparable v, Comparable w) {
        return v.compareTo(w) < 0;
    }

    // 数据交换位置
    private static void exchange(Comparable[] arr, int i, int j) {
        Comparable temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    // 对数组中的元素进行排序
    private static void sort(Comparable[] arr) {
        //1.初始化 辅助数组assist
        assist = new Comparable[arr.length];
        // 2.定义 low high 分别记录数组中的最小索引和最大索引
        int low = 0;
        int high = arr.length - 1;
        // 3.调用重载方法 对数组进行排序
        sort(arr, low, high);
    }

    // 对数组a 中从 low 到high 的元素进行排序
    private static void sort(Comparable[] arr, int low, int high) {
        // 做安全性效验
        if (low >= high) {
            return;
        }

        // 将 low  high 之间的数据 分为两个组
        int mid = low + (high - low) / 2;

        //利用递归分别对两组数据排序
        sort(arr, low, mid);
        sort(arr, mid + 1, high);

        // 最后将两个数组中的数据进行归并
        merge(arr, low, mid, high);
    }


    // 对数组中 从 low 到 mid 为一组  从mid+1 到high 为一组 对这两组进行归并
    private static void merge(Comparable[] arr, int low, int mid, int high) {

        // 定义三个指针  是关键  已经将数据分成了两个部分
        // arrIndex 数组的指针  用于将数据放入到临时数组中
        // leftIndex  左半部分的指针
        // rightIndex  右半部分的指针   这两个指针 是用于 比较 两个部分 将较小的那一个数值放入到数组中 然后将指针后移 直到两个指针的边界 左边是mid 右边是high
        int arrIndex = low;
        int leftIndex = low;
        int rightIndex = mid+1;

        //开始遍历数组 移动leftIndex  rightIndex 指针 比较 数值 将数据放到临时数组中  当其中一个指针到达边界后退出while 循环
        while (leftIndex <= mid && rightIndex <= high) {
            if (less(arr[leftIndex], arr[rightIndex])) {
                assist[arrIndex++] = arr[leftIndex++];
            } else {
                assist[arrIndex++] = arr[rightIndex++];
            }
        }

        // 其中一边的数据已经遍历完毕  我们要将没有遍历完毕的一边数据 按顺序放入到 临时数组中
        while (leftIndex <= mid) {
            assist[arrIndex++] = arr[leftIndex++];
        }
        while (rightIndex <= high) {
            assist[arrIndex++] = arr[rightIndex++];
        }


        // 最后 所有的数据已经按顺序放入到临时数组中   我们按已经排好的数据 copy 到 原数组中
        for (int i=low;i<=high;i++){
            arr[i]=assist[i];
        }

    }

}
